package demo1;
//异常处理机制





//集合框架--->又被称为容器，在定义在java.util包下的一组接口和实现类
//集合类-->所在的包java.util
//stack  栈  ArrayList  顺序表   LinkList 链表   TreeSet + TreeMap   红黑树（特殊的二叉搜索树）
//HashSet HashMap  哈希表

//接口和接口  扩展的关系   LIst Queue  Set Map
//类和接口的关系   实现的关系（implements）
//类和类的关系     继承的关系


//集合框架的重要性  开发 面试
//数据结构

//泛型
//自动装箱 自动拆箱

//算法：数据结构和算法。--》相辅相成
//算法就是将输入转化为输出结果。（或者是--》解决问题的方法）

//数据结构：多总结（写博客）  多刷题  多画图 多打码

//复杂度 时间复杂度+空间复杂度
//如何衡量代码的好坏？ 效率高不高。  时间效率（时间复杂度）+空间效率（空间复杂度）。优先考虑时间复杂度。

//为什么优先考虑时间复杂度呢？  因为空间不是非常贵。怎么考虑时间， 掐表 程序执行前后时间差 都不行

//时间复杂度
//时间复杂度：基本操作的执行次数。表示方法：大O渐近表示法
//   循环
//   for(i = 0;i < n;i++ ) {
//      for(j = 0;;j < n;j++ ) {
//          O(n^2)
//      }
//   }

//   int M = 10;
//   while( M-- > 0) {
//      O(1) 此处的M是一个确定的值
//   }
//   时间复杂度的求法———》
//1--用常数1取代所有常数项
//2--只保留最高阶
//3--如果最高阶的系数部不为1，则将这个项的系数用1取代  3*n^2  用 n^2 取代

//最好时间复杂度
//平均时间复杂度--->看不懂
//最坏时间复杂度---》没有明说，求的就是最坏时间复杂度。

//算时间复杂度不要只看代码，还要结合思想（代码思想，只有明白代码的思想，才能分析正确）

//大话数据结构  + 剑指offer
//例子;
//冒泡排序

//二分查找

//递归的时间复杂度---》等于递归的次数乘每次递归后代码的执行次数
//递归如果套循环 --》 则需要计算循环的次数*递归的次数（有点类似于嵌套循环）


//空间复杂度:临时占用存储空间的大小---》很奇怪，和问题规模的大小没关系
//表示：大O渐近表示法
//



public class Test {
    public void func1(int M,int N) {
        for (int i = 0; i < N; i++) {

        }
        for (int i = 0; i < M; i++) {

        }
        //时间复杂度 O(M + N)
        //两个未知的变量，谁也不可以忽略

    }
    public void func2(int n) {
        n = 100;
        for (int i = 0; i < n; i++) {

        }
        //O(1)
    }

    public void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                //最坏时间复杂度  O(n^2)
                //最好时间复杂度  O(n)
            }
        }
    }

    public int BinarySearch(int[] array,int k) {
        int begin = 0;
        int end = array.length - 1;
        while(begin < end ) {
            int mid = (begin + end)/2;
            if(array[mid] < k) {
                begin = mid + 1;
            }
            if(array[mid] > k) {
                end = mid - 1;
            }else {
                return mid;
            }
        }

        return -1;
        //如果只看代码，不明白代码的思想  n = 2^X
        //O(log以2为底的n)

    }

    //单路递归

    public int fact(int n) {
        return n<2?n:(fact(n-1)*n);
        //空间复杂度 O(n)
    }

    //递归的时间复杂度---》等于递归的次数乘每次递归后代码的执行次数
    //递归如果套循环 --》 则需要计算循环的次数*递归的次数（有点类似于嵌套循环）

    //多路递归 递归求斐波那契数

    int fibonacci(int n) {
        return n<2?n:fibonacci(n-1) + fibonacci(n - 2);
        //空间复杂度 O(n)  不是n^2是因为递归首先一路执行再返回，再调
        //用，此时也是一路执行再返回，再调用，所以最多需要n。
        //计算右边的时候，左边已经递归完了，开辟的栈帧也被回收了
    }

//             f(n)                       1
//      f(n-1)           f(n-2)           2
//  f(n-2)    f(n-3)   f(n-3) f(n-2)      4
// f(n-(n-1))                             2^(n-1)
// 等比数列求和  O(2^n)



    public static void main(String[] args) {
        int n = 10;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

            }
        }
    }
}


//常见的复杂度  O(1) O(logN) O(N) O(logN*N) O(N^2)

